from cmath import inf
from collections import defaultdict
from typing import List


class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        # source 到 target  的最小成本 == 最短路径
        # dis【i】【j】 定义 i 到 j 的最短距离
        dis=[[inf]*26 for _ in range(26)]
        # 自己到自己本身 距离为0
        for i in range(26):
            dis[i][i]=0
        # 存储边 及其 权重
        for x,y,c in zip(original,changed,cost):
            x=ord(x)-ord('a')
            y=ord(y)-ord('a')
            dis[x][y]=min(dis[x][y],c)
        # Floyd算法
        for k in range(26):
            for i in range(26):
                # 如果不存在 i k 这条边 跳过
                if dis[i][k]==inf:
                    continue
                for j in range(26):
                    dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j])
        ans=0
        for x,y in zip(source,target):
            ans+=dis[ord(x)-ord('a')][ord(y)-ord('a')]
        return ans if ans<inf else -1
